package com.LeeCode;

import java.util.Arrays;

/**
 * 毯子覆盖的最多白色砖块数
 */

public class Code2271 {
    public static void main(String[] args) {
        int[][] tiles = {
                {1, 5},
                {10, 11},
                {12, 18},
                {30, 32},
                {20, 25}
        };
        int carpetLen = 10;

        System.out.println(new Code2271().maximumWhiteTiles(tiles, carpetLen));
    }

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, (a, b) -> a[0] - b[0]);
        int ans = 0;
        int cover = 0;
        int left = 0;
        for (int[] tile : tiles) {
            int tl = tile[0];
            int tr = tile[1];
            cover += tr - tl + 1;
            while (tiles[left][1] + carpetLen - 1 < tr) {
                cover -= tiles[left][1] - tiles[left][0] + 1;
                left++;
            }
            int uncover = Math.max(tr - carpetLen + 1 - tiles[left][0], 0);
            ans = Math.max(ans, cover - uncover);
        }
        return ans;
    }
}
